public class Solution208 {

    boolean end;
    Solution208[] children=new Solution208[26];

    public Solution208() {

    }

    public void insert(String word) {
        Solution208 node=this;
        for (char c : word.toCharArray()) {
            if (node.children[c-'a']==null){
                node.children[c-'a']=new Solution208();
            }
            node=node.children[c-'a'];
        }
        node.end=true;
    }

    public boolean search(String word) {
        Solution208 node=this;
        for (char c:word.toCharArray()){
            if (node.children[c-'a']==null){
                return false;
            }
            node=node.children[c-'a'];
        }
        return node.end;
    }

    public boolean startsWith(String prefix) {
        Solution208 node=this;
        for (char c:prefix.toCharArray()){
            if (node.children[c-'a']==null){
                return false;
            }
            node=node.children[c-'a'];
        }
        return true;
    }

    public static void main(String[] args) {
        Solution208 solution208=new Solution208();
        solution208.insert("apple");
        System.out.println(solution208.search("apple"));
        System.out.println(solution208.search("app"));
        System.out.println(solution208.startsWith("app"));
        solution208.insert("app");
        System.out.println(solution208.search("app"));
    }
}
